package com.easy.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Insert57
 * @Description 57. 插入区间
 * @Author zheng
 * @Date 2021/12/6 10:23
 * @Version 1.0
 **/
public class Insert57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0;
        //数组中数据的最大值，比待插入数据的最小值还小，则一定无交集
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }
        //数组中数据的最大值，比待插入数据的最大值还大，但不一定有交集，如果该数据的最小值<= 待插入数据的最大值，就一定有交集
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res.add(newInterval);
        while (i < intervals.length) {
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(new int[res.size()][2]);
    }

    public static void main(String[] args) {
        Insert57 insert57 = new Insert57();
        insert57.insert(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8});
    }

}
